#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>

typedef char STdatatype;
typedef struct Stack
{
	STdatatype* data;
	int top;
	int capacity;
}Stack;

void checkcapacity(Stack* p)
{
	STdatatype* newp;
	if (p->top == p->capacity)
	{
		newp = (STdatatype*)realloc(p->data, sizeof(Stack) * p->capacity * 2);
		if (newp == NULL)
		{
			perror(realloc);
			exit(-1);
		}
		p->data = newp;
		p->capacity *= 2;
	}
	if (p == NULL)
	{
		perror(realloc);
		exit(-1);
	}
}
void StackInit(Stack* p)
{
	assert(p);
	p->data = (STdatatype*)malloc(sizeof(STdatatype) * 4);
	if (p->data == NULL)
	{
		perror(malloc);
		exit(-1);
	}
	p->top = 0;
	p->capacity = 4;
}

void StackPush(Stack* p, STdatatype x)
{
	assert(p);
	checkcapacity(p);
	(p->data)[p->top] = x;
	p->top++;
}

void StackPop(Stack* p)
{
	assert(p);
	assert(p->top);
	p->top--;
}

STdatatype StackTop(Stack* p)
{
	assert(p);
	assert(p->top != 0);
	int top = p->top - 1;
	return (p->data)[top];
}

int StackEmpty(Stack* p)
{
	assert(p);
	return p->top == 0;
}

void StackDestroy(Stack* p)
{
	assert(p);
	free(p->data);
	p->data = NULL;
	p->top = 0;
	p->capacity = 0;
}


bool isValid(char* s) {
	Stack S;
	StackInit(&S);
	while (*s)
	{
		if (*s == '[' || *s == '(' || *s == '{')
		{
			StackPush(&S, *s);
			s++;
		}
		else
		{
			if (StackEmpty(&S))
			{
				StackDestroy(&S);
				return false;
			}
			char top = StackTop(&S);
			StackPop(&S);
			if ((*s == '}' && top != '{') ||
				(*s == ')' && top != '(') ||
				(*s == ']' && top != '['))
			{
				StackDestroy(&S);
				return false;
			}
			else
			{
				s++;
			}
		}
	}
	bool ret = StackEmpty(&S);
	StackDestroy(&S);
	return ret;
}


int main()
{
	Stack S;
	StackInit(&S);
	char arr[] = { "(()){}{}" };
	isValid(arr);
	return 0;
}